Quantum architecture is concerned with the layout of qubits and their allowed interactions in order to be physically realizable as well as to execute algorithms efficiently, such as Shor's factoring algorithm, according to certain resources. Shor's factoring algorithm is a central result in quantum computing with an exponential speed-up over known classical algorithms. Shor's algorithm achieves prime factorization through processing several cases. As a known example of such a quantum-classical separation in performance, much effort has been devoted to realistic implementations of factoring on a quantum computer. Accordingly, there is much current interest in running Shor's factoring algorithm.
Previous approaches to Shor's factoring algorithm assume one dimensional (1D) architectures or arbitrary, long-range interactions. For example, the most mature approaches are trapped ions and superconducting qubits, while a new topological approach that may, for example, be realized using 1D nanowires promises to have much better fault tolerance capabilities. However, 1D quantum architecture may be limited to how many operations may be applied concurrently. For example, 1D quantum architecture may require many movement operations because a qubit may have no more than two neighbors.
Additionally, previous approaches to quantum arithmetic algorithms and Shor's factoring algorithm assume ancillae are expensive (perhaps because of error correction requirements) and that execution time is not the bottleneck, to optimize for circuit width at the expense of circuit depth or size. For example, the transform adder by Draper is an influential idea that uses an inherently quantum idea (changing the basis of addition) so that adding a fixed classical number to a quantum number can be performed only with single-qubit rotations, which can be performed concurrently and in constant-depth. The benefit of being able to perform multiplication through repeated constant-depth additions may be mitigated by the cost of running a quantum Fourier transform to get into and out of the Fourier basis, to get the overflow bit needed for trial subtraction in the VBE scheme for modular reduction named after Vedral, Barenco, and Ekert.
However, there exists a large body of work applying classical ideas to quantum logic. Draper, Kutin, Rains, and Svore describe the first logarithmic-depth adder using carry-lookahead techniques to compute and propagate the carry bit in parallel (in a logarithmic-depth binary tree) among the bit positions to be added. A linear number of qubits are required. Alternatively, Gossett uses carry-save techniques to add numbers in constant-depth and multiply in logarithmic-depth using an encoding, but at a quadratic cost of qubits. The underlying idea of encoded adding, sometimes called a 3-2 adder, derives from Wallace trees.
Choi and Van Meter discussed 2D architectures by designing an adder that runs in Θ(√{square root over (n)})′-depth on 2D NTC using Θ(n)-qubits.
Takahashi and Kunihiro have also discovered a linear-depth and linear-size adder using zero ancillae. Takahashi and Kunihiro also discovered an adder with variable tradeoffs between O(n/d(n)) ancillae and O(d(n))-depth for d(n)=Ω(log n).
After fixing on an adder circuit, it may be straightforward to implement a multiplier as repeated addition of shifted sums (partial products). However, this may not be the simplest approach conceptually, especially when the need to perform modular reduction either after every addition or after each multiplication.
Once the adder building block is decided, many works extrapolate it into a modular exponentiator, through various paths of multiplication and modular reduction. This is the approach taken by Beauregard to construct a cubic-depth quantum period-finder using only 2n+3 qubits on AC, by combining the ideas of Draper's transform adder and Vedral et al.'s modular arithmetic blocks. This approach was subsequently adapted to LNN by Fowler, Devitt, and Hollenberg to achieve exact resource counts for an O(n3)-depth quantum period-finder. Kutin later improved this using an idea from Zalka for approximate multipliers in O(n2)-depth. However, these previous approaches to optimize for circuit width at the expense of circuit depth or size under the assumption that ancillae are expensive and that execution time is not the bottleneck.